import Link.LinkListClass;
import Link.LinkNode;
public class test18 {
    public static LinkListClass<Integer> Union(LinkListClass<Integer>A, LinkListClass<Integer>B){
        LinkListClass<Integer>C=new LinkListClass<Integer>();
        LinkNode<Integer>t=C.head;
        LinkNode<Integer>p=A.head;
        LinkNode<Integer>q=B.head;
        while (p!=null&&q!=null){
            if (p.data<q.data){
                t.next=p;t=p;
                p=p.next;
            }
            else if (q.data< p.data){
                t.next=q;t=q;
                q=q.next;
            }
            else {
                t.next=p;t=p;
                p=p.next;
                q=q.next;
            }
        }
        t.next=null;
        if(p!=null)t.next=p;
        if (q!=null)t.next=q;
        return C;
    }
    public static void main(String[] args) {
        LinkListClass<Integer> listA = new LinkListClass<>();

        LinkListClass<Integer> listB = new LinkListClass<>();


        // 打印原始链表
        System.out.print("List A: ");
        listA.head = new LinkNode<>(1);
        listA.head.next = new LinkNode<>(3);


        System.out.println("List B: ");
        listB.head = new LinkNode<>(2);
        listB.head.next = new LinkNode<>(4);

        // 合并链表
        LinkListClass<Integer> unionList = Union(listA,listB);

        // 打印合并后的链表
        System.out.print("合并后为: ");
        for (int i = 0;i< unionList.size();i++){
            System.out.print(unionList.GetElem(i));
        }//输出null 1 2 3 4
    }
}


